import java.util.List;

// 1、无头单向非循环链表实现
public class SingleLinkedList {
    private class  MyList {
        public int val;
        public MyList next;

        public MyList(int val) {
            this.val = val;
        }
    }
    public MyList head;//null

    //头插法
    public void addFirst(int data) {
        MyList node = new MyList(data);
        node.next = this.head;
        this.head = node;
    }
    //尾插法
    public void addLast(int data) {
        if (this.head == null) {//当没有节点时
            addFirst(data);
            return;
        }
        MyList node = new MyList(data);
        MyList run = this.head;
        while (run.next != null) {
            run = run.next;
        }
        run.next = node;
    }
    //任意位置插入,第一个数据节点为0号下标
    public boolean addIndex(int index,int data) {
        if (index < 0) {//下标小于0
            return false;
        }
        if (index == 0) {
            addFirst(data);
            return true;
        }
        MyList run = this.head;//在run的下一个节点插入
        while (index-- > 1) {
            run = run.next;
            if (run.next == null) {//下标超过
                return false;
            }
        }
        MyList node = new MyList(data);
        node.next = run.next;
        run.next = node;
        return true;
    }
    //查找是否包含关键字key是否在单链表当中
    public boolean contains(int key) {
        MyList run = this.head;
        while (run != null) {
            if (run.val == key) {
                return true;
            }
            run = run.next;
        }
        return false;

    }
    //删除第一次出现关键字为key的节点
    public void remove(int key) {
        MyList run = this.head;
        MyList runPrev = null;//run的前一个
        while (run != null) {
            if (run.val == key) {
                if (runPrev == null) {//删除第一个
                    this.head = run.next;
                }else {
                    runPrev.next = run.next;
                }
                return;
            }
            runPrev = run;
            run = run.next;
        }
        System.out.println("找不到要删除的:" + key);
    }
    //删除所有值为key的节点
    public void removeAllKey(int key) {
        MyList run = this.head;
        MyList runPrev = null;//run的前一个
        while (run != null) {
            if (run.val == key) {
                if (runPrev == null) {//删除第一个
                    this.head = run.next;
                }else {
                    runPrev.next = run.next;
                }
                //删除元素的 走法
                run = run.next;
                continue;
            }
            runPrev = run;//不删除元素的 走法
            run = run.next;
        }
    }
    //得到单链表的长度
    public int size() {
        int cont = 0;
        MyList run = head;
        while (run != null) {
            cont++;
            run = run.next;
        }
        return cont;
    }
    public void display() {
        MyList run = head;
        while (run != null) {
            System.out.print(run.val + " ");
            run = run.next;
        }
        System.out.println();
    }
    public void clear() {
        this.head = null;
    }
}
